Floorplanning is the process of placing functional devices ("functions," also referred to as modules, elements, blocks or functional blocks) on a chip, and allocating interconnection space among them, so as to minimize the actual chip area required to encompass such functions and their interconnections, and to maximize the probability that such interconnections can be routed within that area.
A function consists of a discrete logic and/or memory element, or any combination of such elements. It may be as simple as an inverter or a flip-flop, consisting of one or only a few transistors, or as complex as a shift register, an ALU or even an entire microprocessor, consisting of hundreds of thousands of transistors.
From a mathematical point of view, both formulating and solving the floorplanning problem are quite difficult. A precise mathematical solution essentially cannot be obtained. Heuristic algorithms are therefore employed to approximate the optimum solution to the floorplanning problem.
Moreover, due to the increasing complexity of chip designs, necessitating more and more logic and/or memory elements per unit area, the complexity of the floorplanning problem has increased dramatically. It is, therefore, extremely advantageous to automate this process in some fashion.
Prior to the floorplanning process itself, which involves the placement of functions on a chip, the chip's logic must be designed. Logic designers generally employ hierarchical design techniques to determine the appropriate selection and interconnection of logic and/or memory devices which will enable the chip to perform the desired function. These techniques involve describing the chip's functionality at various "levels of abstraction," ranging from the most general function performed by the chip to the precise functions performed by each logic and/or memory element on the chip.
Thus, a logic designer's hierarchy consists of N levels of functions, where N is an integer (N.gtoreq.1) representing the number of hierarchical levels of functionality in the chip, the first level being the chip itself, and where n is an integer (1.ltoreq.n.ltoreq.N) representing the level of any particular function in the hierarchy.
A "parent" function at the (n)th level of the hierarchy is defined as a plurality of (n+1)st level "children" functions, each of which is a "child" function. For example, a microprocessor at the (n)th level might be defined as the parent of the following (n+1)st level children: an ALU, a series of registers, a bus and various other functions (each of which may or may not have a plurality of (n+2)d level children, and so on).
Each child function which is not also a parent function (i.e., which has no children) is referred to as a "terminal" (or "leaf") function. Each terminal function is connected to at least one other terminal function, such connection commonly being referred to as a "net." A series of nets, each of which defines a plurality of interconnected functions, is commonly referred to as a "net list."
Note that lower levels of the hierarchy are commonly denoted by successively higher numbers. Thus, while level 1 refers to the top (chip) level of the hierarchy, levels 2, 3 and 4 constitute successively "lower" levels of the hierarchy.
Previous floorplanning techniques roughly fall into two basic categories: (1) "flat" floorplanners, which attempt to minimize space at only one level (the "level" which is created when the hierarchy is flattened by omitting all but the terminal functions), by placing only terminal functions; and (2) "top-automated" floorplanners, which automate the floorplanning process at only the top level, by placing only 2d level functions.
In essence, there are three significant floorplanning obstacles which previous methods have not overcome:
(1) Hierarchical Estimation of Unknown Function Area When the floorplanning process begins, the precise area of each function may not be known, because certain functions have not yet been laid out. Only after the elements of a given function have been laid out, taking all interconnections into account, can the precise area of that function be determined.
Although the interconnection area within a function (whose elements have not yet been laid out) is the dominant factor in determining the overall area occupied by that function, previous methods do not include means for estimating this interconnection area (and thus the area of the function) throughout the hierarchy of functions. Such methods are limited to estimating the interconnection area of a "flat" design by multiplying the total area of the functions themselves by a statistically determined percentage.
(2) Maintenance of Modularity Once a chip's logic has been designed in a hierarchical fashion (with each parent defined as a plurality of its children), it is important that the floorplanning process not interfere with or destroy the logic designer's approach. Flat floorplanners place only terminal functions, which may occur at many different levels of the hierarchy. Such floorplanners may well destroy the hierarchy imposed by the logic designer, by placing children outside of the area occupied by their parent.
Logic designers often desire to cluster various functions (children) together into a larger function (parent). This is done for a variety of reasons, such as the speed of interaction between two functions, which reasons are generally not factored into the floorplanning process. Floorplanning below the level of the larger (parent) function, however, may result in the unclustering of the component (children) functions, thereby eliminating the functional advantages created by the logic designer's hierarchical design.
(3) Hierarchical Interconnection of Functions By far the most significant obstacle to achieving the optimum floorplan is the fact that optimizing the floorplan at any given level in the hierarchy requires knowledge of functional interconnections at other levels. Because logic and/or memory elements are interconnected throughout the logic designer's hierarchy (not merely at the bottom level), optimum floorplanning at any level requires a hierarchical approach which takes these inter-level interconnections into account.
Previous floorplanning methods are not hierarchical, in that they do not take into account this interaction among functions at different levels in the hierarchy. Flat floorplanning techniques consider only the "level" composed of terminal functions. There may be such a large number of these terminal functions that even automated techniques require too much time to be considered feasible.
Moreover, as discussed above, floorplanning at this "level" may well violate the hierarchy imposed by the logic designer. The need for truly hierarchical floorplanning is perhaps best evidenced by the desire of companies to classify essentially flat floorplanning techniques as hierarchical. See, e.g., McLeod, Jonah, "Now Designers Can Skip Floor-Planning Details," Electonics, April 30, 1987, pp. 61-62; and Ueda, Kazuhiro, et al., "CHAMP: Chip Floorplanning For Hierarchical VLSI Layout Design," IEEE Transactions on Computer-Aided Design, Vol. CAD-4, No. 1, January, 1985, pp. 12-22.
Top-automated floorplanning techniques also only operate at one (the top) level. Floorplanning even at this level does not adequately take into account the placement and interconnection of functions at lower levels, because the placement of such functions at these lower levels is determined manually before this automated process even begins. Thus, automated floorplanning at the top level is constrained to be suboptimal to the extent that the manual placement of functions at lower levels is suboptimal.
Previous methods do, however, include single-level floorplanning techniques. One such technique involves "partitioning" the functions into two groups to minimize the number of interconnections between the groups. This procedure is recursively applied to force heavily connected functions to be placed next to one another, resulting in the formation of clusters of functions which minimize required routing space. See Kernighan, B. W. and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," The Bell System Technical Journal, February, 1970, pp. 291-307.
Another technique (often used in conjunction with partitioning) involves "slicing" or dissecting the chip area into rectangular "slicing regions" (regions within which each of the partitioned groups of functions can be placed), and then placing each partitioned group of functions in one of such regions, so as to minimize the wasted area, and hence the total chip area. See Otten, Ralph, H. J. M., "Layout Structures," IBM Research Report, No. RC 9657 (#42647), October 28, 1982.
Such single-level floorplanning methods simply do not, however, take into account the constraints imposed by the logic designer's hierarchy, such as the hierarchical clustering of children functions within their parent functions, and the interconnection of functions across the various levels of that hierarchy.